/**
 * 小山寻径,5个格子以内还可以，用的是递归。比较低级。
 * 可以标志人物的可移动范围
*将来在XZ平面也一样的用
ok 稍微改装则工作正常
*/
package kgame5.kgu.ai.hill {
import kgame5.kutil.*;

public class HillPathFinder{
	
	///////////////////////////////////////
	//////////////////////PathFinder/////////////////////////////
	public static function FindPath (BGBarData:Array, startCellX:int, startCellY:int, endCellX:int, endCellY:int, valiRange:int):Array {
		//寻经时标记脚印的搜索范围是根据目的地和原来地点的距离来动态调整的，保证是最合适的搜索范围
		//int valiRange = (Math.abs(startCellX - endCellX) + Math.abs(startCellY - endCellY))+1;
		//valiRange=8;//要是小范围的搜索的话，为了保证在复杂障碍物中能穿过，在不影响效率的情况下把他提高到6
		//T.p("开始寻路径"+" "+startCellX+" "+startCellY+" "+endCellX+" "+endCellY);
		//T.TraceArray2("barData",BGBarData);
		
		var flag:Array = Util.NewArray2_Int (BGBarData.length, BGBarData[0].length);
		MarkMoveRange (BGBarData, startCellX, startCellY, valiRange, flag);
		//T.TraceArray2("flag",flag);
		
		var a2Route:Array= GetMovePath (flag, startCellX, startCellY, endCellX, endCellY);
		//T.TraceArray2("a2Route",a2Route);
		
		return a2Route;
	}
	//标志可移动范围BG.Flag,给我的活动范围打上标志，标志出哪里能走哪里不能走
	//BGBarData 0表示的是可走,flag里0表示不可走
	//!!注意这里的col,row一定要是整数！
	public static function MarkMoveRange (BGBarData:Array, col:int, row:int, range:int, flag:Array) {
		//标记脚印，按顺序，如：7，6，5，4，3，2，1
		if (range > flag[row][col]) {
			flag[row][col] = range;
		}
		if (range == 0) {
			return;
		}
		if (row > 0 && BGBarData[row - 1][col] == 0) {
			//可上移
			MarkMoveRange (BGBarData, col, row - 1, range - 1, flag);
		}
		if (row < BGBarData.length - 1 && BGBarData[row + 1][col] == 0) {
			//可下移
			MarkMoveRange (BGBarData, col, row + 1, range - 1, flag);
		}
		if (col > 0 && BGBarData[row][col - 1] == 0) {
			//可左移
			MarkMoveRange (BGBarData, col - 1, row, range - 1, flag);
		}
		if (col < BGBarData[0].length - 1 && BGBarData[row][col + 1] == 0) {
			//可右移
			MarkMoveRange (BGBarData, col + 1, row, range - 1, flag);
		}
	}
	//
	//====================================最好的寻径============================================
	//获得移动路线 ，返回的是一个2维数组
	public static function GetMovePath (Flag:Array, startCellX:int, startCellY:int, endCellX:int, endCellY:int):Array {
		try {
			var vector:Array = null;
			var Pos:Array = new Array ();
			Pos[0] = endCellX;
			Pos[1] = endCellY;
			if (startCellX == endCellX && startCellY == endCellY) {
				vector = new Array ();
				vector.push (Pos);
				return vector;
			}
			var flag0:int = 0;
			var flag1:int = 0;
			var flag2:int = 0;
			var flag3:int = 0;
			if (endCellY > 0) {
				flag0 = Flag[endCellY - 1][endCellX];
			}
			if (endCellY < Flag.length - 1) {
				flag1 = Flag[endCellY + 1][endCellX];
			}
			if (endCellX > 0) {
				flag2 = Flag[endCellY][endCellX - 1];
			}
			if (endCellX < Flag[0].length - 1) {
				flag3 = Flag[endCellY][endCellX + 1];
			}
			var maxFlag:int =  Math.max (Math.max (flag0, flag1), Math.max (flag2, flag3));
			//如果不可到达，即四周都是不可走的了,则返回空
			if(maxFlag==0){
				trace("死胡同啊");
				return null;
			}
			
			if (maxFlag == flag0){
				vector = GetMovePath (Flag, startCellX, startCellY, endCellX, endCellY - 1);
			} else if (maxFlag == flag1) {
				vector = GetMovePath (Flag, startCellX, startCellY, endCellX, endCellY + 1);
			} else if (maxFlag == flag2) {
				vector = GetMovePath (Flag, startCellX, startCellY, endCellX - 1, endCellY);
			} else if (maxFlag == flag3) {
				vector = GetMovePath (Flag, startCellX, startCellY, endCellX + 1, endCellY);
			}
			vector.push (Pos);
			return vector;
		} catch (e) {
			trace ("error");
			return null;
		}
		return null;
	}
	
	///////////////////////////////////////
}
}